English+GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Sortierverfahren</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Sortierverfahren</h1>

</header>

</div>

Unter einem Sortierverfahren versteht man in der Informatik einen <a href="Algorithmus" title="Algorithmus">Algorithmus</a>, der dazu dient, ein <a href="Tupel" title="Tupel">Tupel</a> (i. Allg. ein <a href="Array_(Datentyp)" title="Array (Datentyp)">Array</a>) zu <a href="Sortieren" class="mw-redirect" title="Sortieren">sortieren</a>. Voraussetzung ist, dass auf der <a href="Menge_(Mathematik)" title="Menge (Mathematik)">Menge</a> der Elemente eine <a href="Strenge_schwache_Ordnung" title="Strenge schwache Ordnung">strenge schwache Ordnung</a> definiert ist („kleiner-gleich“), z. B. die <a href="Lexikographische_Ordnung" title="Lexikographische Ordnung">lexikographische Ordnung</a> von Zeichenketten oder die numerische Ordnung von Zahlen.

Es gibt verschiedene Sortierverfahren, die unterschiedlich effizient arbeiten bezüglich der <a href="Zeitkomplexit%C3%A4t" title="Zeitkomplexität">Zeitkomplexität</a> (Anzahl der nötigen Operationen) sowie der <a href="Platzkomplexit%C3%A4t" title="Platzkomplexität">Platzkomplexität</a> (zusätzlich zum Eingabe-Array benötigter weiterer <a href="Arbeitsspeicher" title="Arbeitsspeicher">Speicherplatz</a>). Die Komplexität eines Algorithmus wird üblicherweise in der <a href="Landau-Notation" class="mw-redirect" title="Landau-Notation">Landau-Notation</a> dargestellt (s. u. Ausdrücke wie <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (n\cdot \log(n))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"> (Theta) oder stilisiertes „Oh“, Omega groß, Omega klein). Die Zeitkomplexität hängt bei einigen Sortierverfahren von der anfänglichen Anordnung der Werte im Array ab, man unterscheidet dann zwischen Best Case (bei günstigster „Vorsortierung“), Average Case (Normalfall) und Worst Case (schlechtester Fall ~ die Werte sind „maximal ungünstig“).

Häufig sind zusätzliche Faktoren zu beachten, die Einfluss auf Zeit- oder Platzkomplexität haben, zum Beispiel langsamer Zugriff auf extern liegende Daten, begrenzte Größe des Arbeitsspeichers oder ähnliches.

Man unterscheidet zudem zwischen <a href="Stabiles_Sortierverfahren" class="mw-redirect" title="Stabiles Sortierverfahren">stabilen</a> und instabilen Sortierverfahren. Stabile Sortierverfahren sind solche, die die relative Reihenfolge von Elementen, die bezüglich der Ordnung äquivalent sind, nicht verändern, während instabile Sortierverfahren dies nicht garantieren. Ist beispielsweise die Mitarbeiterliste einer Firma nach Nachname geordnet und wird anschließend nach Alter (in Jahren) sortiert, so bleibt die (Nachnamen-)Reihenfolge unter gleichaltrigen Mitarbeitern bei einem stabilen Sortierverfahren bestehen.

Zudem unterscheidet man zwischen Sortierverfahren, die <a href="In-place" class="mw-redirect" title="In-place">in-place</a> (auch <a href="In_situ" title="In situ">in situ</a>) arbeiten, d. h. der zusätzliche Speicherbedarf ist unabhängig von der Anzahl der zu sortierenden Elemente (also konstant und meist gering), und solchen, bei denen er abhängig ist (<a href="Out-of-place-Algorithmus" title="Out-of-place-Algorithmus">out-of-place</a> oder <a href="Ex_situ" title="Ex situ">ex situ</a>).

Und man unterscheidet auch zwischen natürlichen Sortierverfahren, die bei vorsortierten Daten schneller arbeiten als bei unsortierten Daten, und solchen, die es nicht tun. Algorithmen, bei denen der <a href="Kontrollfluss" title="Kontrollfluss">Kontrollfluss</a> von den Daten abhängt, nennt man <a href="Adaptiver_Sortieralgorithmus" title="Adaptiver Sortieralgorithmus">adaptiv</a> und dementsprechend Sortierverfahren, die nicht von den Eingabedaten abhängen, nicht-adaptiv. Nicht-adaptive Algorithmen sind demnach besonders interessant für Hardware-Implementierungen.

Manuelles Sortieren (etwa von Karteikarten) sowie elektro-mechanische Sortierverfahren (z. B. für <a href="Lochkarte" title="Lochkarte">Lochkarten</a>) entsprechen meist einem der hier beschriebenen <a href="Software" title="Software">softwarebasierten</a> Sortierverfahren, oder Mischtypen.

<div class="mw-heading mw-heading2"><h2 id="Vergleichsbasiertes_Sortieren">Vergleichsbasiertes Sortieren</h2></div>

Allgemeine Verfahren basieren auf dem paarweisen Vergleich der zu sortierenden Elemente, ob das eine Element „kleiner“ als, „größer“ als oder „gleich(groß)“ wie das andere Element ist. Bei der Komplexitätsanalyse wird davon ausgegangen, dass der Aufwand zum Vergleich zweier Elemente konstant ist.

Die Tabelle zeigt den Aufwand für unterschiedliche Sortierverfahren.

<th>Sortierverfahren</th>

<th>Günstigster Fall („Best-Case“)</th>

<th>Mittlerer Fall („Average-Case“)</th>

<th>Ungünstigster Fall („Worst-Case“)</th>

<th><a href="Stabiles_Sortierverfahren" class="mw-redirect" title="Stabiles Sortierverfahren">Stabil</a></th>

<th>Zusätzlicher Speicherbedarf

</th></tr>

<tr>

<td><a href="Binary_Tree_Sort" title="Binary Tree Sort">Binary Tree Sort</a> (höhen-balanciert)</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a6351206e27071559aa4472579095994f650d76b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.012ex; height:2.843ex;" alt="{\displaystyle \Theta (n)}" loading="lazy">

</td></tr>

<tr>

<td><a href="Binary_Tree_Sort" title="Binary Tree Sort">Binary Tree Sort</a></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/215877752c4f392a7276328d4d37709bf7c3f55d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.066ex; height:3.176ex;" alt="{\displaystyle \Theta (n^{2})}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a6351206e27071559aa4472579095994f650d76b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.012ex; height:2.843ex;" alt="{\displaystyle \Theta (n)}" loading="lazy">

</td></tr>

<tr>

<td><a href="Bubblesort" title="Bubblesort">Bubblesort</a></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a6351206e27071559aa4472579095994f650d76b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.012ex; height:2.843ex;" alt="{\displaystyle \Theta (n)}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/215877752c4f392a7276328d4d37709bf7c3f55d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.066ex; height:3.176ex;" alt="{\displaystyle \Theta (n^{2})}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/215877752c4f392a7276328d4d37709bf7c3f55d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.066ex; height:3.176ex;" alt="{\displaystyle \Theta (n^{2})}" loading="lazy"></td>

<td>–

</td></tr>

<tr>

<td><a href="Combsort" title="Combsort">Combsort</a></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4441d9689c0e6b2c47994e2f587ac5378faeefba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.108ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n^{2})}" loading="lazy"></td>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4441d9689c0e6b2c47994e2f587ac5378faeefba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.108ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n^{2})}" loading="lazy"></td>

<td>–

</td></tr>

<tr>

<td><a href="Gnomesort" title="Gnomesort">Gnomesort</a></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a6351206e27071559aa4472579095994f650d76b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.012ex; height:2.843ex;" alt="{\displaystyle \Theta (n)}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/215877752c4f392a7276328d4d37709bf7c3f55d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.066ex; height:3.176ex;" alt="{\displaystyle \Theta (n^{2})}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/215877752c4f392a7276328d4d37709bf7c3f55d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.066ex; height:3.176ex;" alt="{\displaystyle \Theta (n^{2})}" loading="lazy"></td>

<td>–

</td></tr>

<tr>

<td><a href="Heapsort" title="Heapsort">Heapsort</a></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

<td>–

</td></tr>

<tr>

<td><a href="Insertionsort" title="Insertionsort">Insertionsort</a></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a6351206e27071559aa4472579095994f650d76b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.012ex; height:2.843ex;" alt="{\displaystyle \Theta (n)}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/215877752c4f392a7276328d4d37709bf7c3f55d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.066ex; height:3.176ex;" alt="{\displaystyle \Theta (n^{2})}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/215877752c4f392a7276328d4d37709bf7c3f55d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.066ex; height:3.176ex;" alt="{\displaystyle \Theta (n^{2})}" loading="lazy"></td>

<td>–

</td></tr>

<tr>

<td><a href="Introsort" title="Introsort">Introsort</a></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

<td>–

</td></tr>

<tr>

<td><a href="Merge_Insertion" title="Merge Insertion">Merge Insertion</a></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"><a href="#cite_note-2">[2]</a></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

<td>–

</td></tr>

<tr>

<td><a href="Mergesort" title="Mergesort">Mergesort</a></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

<td>Implementierung auf verketteter Liste: in-place übliche Implementierungen (auf Array): <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a6351206e27071559aa4472579095994f650d76b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.012ex; height:2.843ex;" alt="{\displaystyle \Theta (n)}" loading="lazy"> Es gibt in-place auf Array, jedoch dann Zeitkomplex. = n * (log n) * (log n) .

</td></tr>

<tr>

<td><a href="Mergesort#Natural_Mergesort" title="Mergesort">Natural Mergesort</a></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a6351206e27071559aa4472579095994f650d76b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.012ex; height:2.843ex;" alt="{\displaystyle \Theta (n)}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

<td>–

</td></tr>

<tr>

<td><a href="Quicksort" title="Quicksort">Quicksort</a></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/215877752c4f392a7276328d4d37709bf7c3f55d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.066ex; height:3.176ex;" alt="{\displaystyle \Theta (n^{2})}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (\log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7e7de5a3708e1af13d46575c1eb97e84235a39c8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.793ex; height:2.843ex;" alt="{\displaystyle \Theta (\log(n))}" loading="lazy">, übliche Implementierungen benötigen meist mehr

</td></tr>

<tr>

<td><a href="Samplesort" title="Samplesort">Samplesort</a></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/215877752c4f392a7276328d4d37709bf7c3f55d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.066ex; height:3.176ex;" alt="{\displaystyle \Theta (n^{2})}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a6351206e27071559aa4472579095994f650d76b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.012ex; height:2.843ex;" alt="{\displaystyle \Theta (n)}" loading="lazy">

</td></tr>

<tr>

<td><a href="Selectionsort" title="Selectionsort">Selectionsort</a></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/215877752c4f392a7276328d4d37709bf7c3f55d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.066ex; height:3.176ex;" alt="{\displaystyle \Theta (n^{2})}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/215877752c4f392a7276328d4d37709bf7c3f55d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.066ex; height:3.176ex;" alt="{\displaystyle \Theta (n^{2})}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/215877752c4f392a7276328d4d37709bf7c3f55d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.066ex; height:3.176ex;" alt="{\displaystyle \Theta (n^{2})}" loading="lazy"></td>

<td>–

</td></tr>

<tr>

<td><a href="Shakersort" title="Shakersort">Shakersort</a> (Cocktailsort)</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a6351206e27071559aa4472579095994f650d76b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.012ex; height:2.843ex;" alt="{\displaystyle \Theta (n)}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/215877752c4f392a7276328d4d37709bf7c3f55d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.066ex; height:3.176ex;" alt="{\displaystyle \Theta (n^{2})}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/215877752c4f392a7276328d4d37709bf7c3f55d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.066ex; height:3.176ex;" alt="{\displaystyle \Theta (n^{2})}" loading="lazy"></td>

<td>–

</td></tr>

<tr>

<td><a href="Shellsort" title="Shellsort">Shellsort</a></td>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\cdot \log(n)^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7725a6381c8a9a15a2330278e652832375998f95.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.963ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n\cdot \log(n)^{2})}" loading="lazy"><a href="#cite_note-shellsort-3">[3]</a></td>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\cdot \log(n)^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7725a6381c8a9a15a2330278e652832375998f95.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.963ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n\cdot \log(n)^{2})}" loading="lazy"><a href="#cite_note-shellsort-3">[3]</a></td>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\cdot \log(n)^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7725a6381c8a9a15a2330278e652832375998f95.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.963ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n\cdot \log(n)^{2})}" loading="lazy"><a href="#cite_note-shellsort-3">[3]</a></td>

<td>–

</td></tr>

<tr>

<td><a href="Smoothsort" title="Smoothsort">Smoothsort</a></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a6351206e27071559aa4472579095994f650d76b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.012ex; height:2.843ex;" alt="{\displaystyle \Theta (n)}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

<td>–

</td></tr>

<tr>

<td><a href="Stoogesort" title="Stoogesort">Stoogesort</a></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (n^{2,7})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0ebe2a8202b747be2ab554690866f1248719d43a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.216ex; height:3.176ex;" alt="{\displaystyle \Omega (n^{2,7})}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (n^{2,7})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0ebe2a8202b747be2ab554690866f1248719d43a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.216ex; height:3.176ex;" alt="{\displaystyle \Omega (n^{2,7})}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (n^{2,7})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0ebe2a8202b747be2ab554690866f1248719d43a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.216ex; height:3.176ex;" alt="{\displaystyle \Omega (n^{2,7})}" loading="lazy"></td>

<td>–

</td></tr>

<tr>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/215877752c4f392a7276328d4d37709bf7c3f55d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.066ex; height:3.176ex;" alt="{\displaystyle \Theta (n^{2})}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/215877752c4f392a7276328d4d37709bf7c3f55d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.066ex; height:3.176ex;" alt="{\displaystyle \Theta (n^{2})}" loading="lazy"></td>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/215877752c4f392a7276328d4d37709bf7c3f55d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.066ex; height:3.176ex;" alt="{\displaystyle \Theta (n^{2})}" loading="lazy"></td>

<td>–

</td></tr>

<tr>

<td><a href="Timsort" title="Timsort">Timsort</a></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a6351206e27071559aa4472579095994f650d76b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.012ex; height:2.843ex;" alt="{\displaystyle \Theta (n)}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/979b36c5e2530b933de455c443d5c37997b82871.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.867ex; height:2.843ex;" alt="{\displaystyle \Theta (n\cdot \log(n))}" loading="lazy"></td>

<td>–

</td></tr>

<tr>

<td><a href="Bogosort" title="Bogosort">Bogosort</a>

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a6351206e27071559aa4472579095994f650d76b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.012ex; height:2.843ex;" alt="{\displaystyle \Theta (n)}" loading="lazy">

</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\cdot n!)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a54435fcaebb415ae77acdafbf9a8a48dd7e8b4b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.775ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n\cdot n!)}" loading="lazy"><a href="#cite_note-bogo-4">[4]</a>

</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n\cdot n!)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a54435fcaebb415ae77acdafbf9a8a48dd7e8b4b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.775ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n\cdot n!)}" loading="lazy"><a href="#cite_note-bogo-4">[4]</a>

</td>

<td>nein

</td>

<td>–

</td></tr>

<tr>

<td><a href="Slowsort" title="Slowsort">Slowsort</a>

</td>

<mrow>

<msup>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega \left(n^{\frac {\log(n)}{(2+\varepsilon )}}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/226f867e8887e662bdc942f3e1c0914522df2394.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:11.755ex; height:7.509ex;" alt="{\displaystyle \Omega \left(n^{\frac {\log(n)}{(2+\varepsilon )}}\right)}" loading="lazy"><a href="#cite_note-:slowSort-5">[5]</a>

</td>

<mrow>

<msup>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega \left(n^{\frac {\log(n)}{(2+\varepsilon )}}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/226f867e8887e662bdc942f3e1c0914522df2394.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:11.755ex; height:7.509ex;" alt="{\displaystyle \Omega \left(n^{\frac {\log(n)}{(2+\varepsilon )}}\right)}" loading="lazy"><a href="#cite_note-:slowSort-5">[5]</a>

</td>

<mrow>

<msup>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega \left(n^{\frac {\log(n)}{(2+\varepsilon )}}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/226f867e8887e662bdc942f3e1c0914522df2394.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:11.755ex; height:7.509ex;" alt="{\displaystyle \Omega \left(n^{\frac {\log(n)}{(2+\varepsilon )}}\right)}" loading="lazy"><a href="#cite_note-:slowSort-5">[5]</a>

</td>

<td>nein

</td>

<td>–

</td></tr></tbody></table>

<li id="cite_note-bintree-1"><a href="#cite_ref-bintree_1-0">↑</a> Für die stabile Version s. die Bemerkung im Artikel <a href="Binary_Tree_Sort" title="Binary Tree Sort">Binary Tree Sort</a>.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> Florian Stober, Armin Weiß: <a rel="nofollow" class="external text" href="https://arxiv.org/abs/1905.09656v1">On the Average Case of MergeInsertion.</a> Abgerufen am 20. Januar 2022.<span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3ASortierverfahren&rft.title=On+the+Average+Case+of+MergeInsertion&rft.description=On+the+Average+Case+of+MergeInsertion&rft.identifier=https%3A%2F%2Farxiv.org%2Fabs%2F1905.09656v1&rft.creator=Florian+Stober%2C+Armin+Wei%C3%9F">

</li>

<li id="cite_note-shellsort-3">↑ <a href="#cite_ref-shellsort_3-0">a</a> <a href="#cite_ref-shellsort_3-1">b</a> <a href="#cite_ref-shellsort_3-2">c</a> Für die (im Worst Case) beste bekannte Distanzfolge.

</li>

<li id="cite_note-bogo-4">↑ <a href="#cite_ref-bogo_4-0">a</a> <a href="#cite_ref-bogo_4-1">b</a> <a href="Erwartungswert" title="Erwartungswert">Erwartete</a> Laufzeit.

</li>

<li id="cite_note-:slowSort-5">↑ <a href="#cite_ref-:slowSort_5-0">a</a> <a href="#cite_ref-:slowSort_5-1">b</a> <a href="#cite_ref-:slowSort_5-2">c</a> Für ein beliebiges <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon >0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon >0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e04ec3670b50384a3ce48aca42e7cc5131a06b12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.344ex; height:2.176ex;" alt="{\displaystyle \varepsilon >0}" loading="lazy">, siehe <a href="Slowsort" title="Slowsort">Slowsort</a>.

</li>

</ol>

<div class="mw-heading mw-heading2"><h2 id="Nicht-vergleichsbasiertes_Sortieren">Nicht-vergleichsbasiertes Sortieren</h2></div>

Bei Sortierverfahren, die nicht auf Vergleichen beruhen, bei denen die zu sortierenden Objekte also nicht untereinander auf „kleiner“, „größer“ oder „gleich“ verglichen werden, kann bei entsprechend konditionierter Eingabe erreicht werden, dass die benötigte Zeit nur linear mit der Anzahl der zu sortierenden Elemente ansteigt. Bei großen Anzahlen zu sortierender Datensätze sind diese Algorithmen den vergleichsbasierten Verfahren überlegen, sofern sie (wegen des zusätzlichen Speicherbedarfs) angewendet werden können.

Sie können allerdings nur für numerische Datentypen verwendet werden (oder unter der Bedingung, dass der Datentyp in annehmbarem Aufwand auf Zahlenwerte gleicher Anordnung abgebildet werden kann).

Dabei wird implizit angenommen, dass die Länge des Schlüssels beschränkt ist, so dass seine Verwertung in konstanter Zeit möglich ist.

Das Senken der Zeitkomplexität von der Elementanzahl wird erkauft durch eine zusätzliche zeitliche Abhängigkeitsgröße (meist der Schlüssellänge oder der Anzahl möglicher Schlüsselwerte), oft auch durch erheblichen zusätzlichen Speicherbedarf.

<th>Sortierverfahren</th>

<th>Stabil</th>

<th>Zusätzlicher Speicherbedarf

</th></tr>

<tr>

<td><a href="Bucketsort" title="Bucketsort">Bucketsort</a></td>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}\left(n+k\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d17046863124cf70150c9da94a9e158309c3827a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.493ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}\left(n+k\right)}" loading="lazy">

</td>

<td>ja

</td>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}\left(n+k\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d17046863124cf70150c9da94a9e158309c3827a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.493ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}\left(n+k\right)}" loading="lazy">

</td></tr>

<tr>

<td><a href="Countingsort" title="Countingsort">Countingsort</a></td>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}\left(n+k\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d17046863124cf70150c9da94a9e158309c3827a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.493ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}\left(n+k\right)}" loading="lazy">

</td>

<td>ja

</td>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}\left(n+k\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d17046863124cf70150c9da94a9e158309c3827a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.493ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}\left(n+k\right)}" loading="lazy">

</td></tr>

<tr>

<td><a href="Radixsort" title="Radixsort">Radixsort</a></td>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}\left(n\cdot l\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d8ae9098e172a24cb12643397659ca17bad17202.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.813ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}\left(n\cdot l\right)}" loading="lazy">

</td>

<td>ja

</td>

</mrow>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}\left(n\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a0c38b7eda49c42d3436db098d1f96655a9624e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.441ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}\left(n\right)}" loading="lazy">

</td></tr>

<tr>

<td>MSD <a href="Radixsort" title="Radixsort">Radixsort</a></td>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}\left(n\cdot l\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d8ae9098e172a24cb12643397659ca17bad17202.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.813ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}\left(n\cdot l\right)}" loading="lazy">

</td>

<td>nein

</td>

</mrow>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}\left(1\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2f1ed5fe4d59a547563c0c55dd4554c040f4efa9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.209ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}\left(1\right)}" loading="lazy">, in-place

</td></tr>

<tr>

<td><a href="Flashsort" title="Flashsort">Flashsort</a></td>

</mrow>

<mrow>

</mrow>

</mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}\left(n\right)\,..\,{\mathcal {O}}\left(n^{2}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/951dd4ac98fa3c776052371979558c2bfce26bd7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:15.486ex; height:3.343ex;" alt="{\displaystyle {\mathcal {O}}\left(n\right)\,..\,{\mathcal {O}}\left(n^{2}\right)}" loading="lazy">

</td>

<td>nein

</td>

</mrow>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}\left(1\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2f1ed5fe4d59a547563c0c55dd4554c040f4efa9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.209ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}\left(1\right)}" loading="lazy">

</td></tr></tbody></table>

Dabei stellt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> die Anzahl der Elemente dar, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> die Anzahl der möglichen Werte und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy"> die Anzahl der Stellen des längsten Schlüssels.

<div class="mw-heading mw-heading2"><h2 id="Sortierung_nach_Beziehungen">Sortierung nach Beziehungen</h2></div>

Wenn nicht mehr nach Eigenschaften, sondern nur noch nach paarweisen Beziehungen sortiert werden kann, so spricht man von einer <a href="Topologische_Sortierung" title="Topologische Sortierung">topologischen Sortierung</a>. Dies ist beispielsweise der Fall, wenn Aufgaben erledigt werden müssen, manche Aufgaben aber unbedingt vor anderen durchzuführen sind, bei anderen jedoch die Reihenfolge keine Rolle spielt.

Für das topologische Sortieren gibt es Algorithmen, deren Laufzeit von der Anzahl der Beziehungen abhängt. Topologisches Sortieren ist nicht möglich, wenn gegenseitige (zyklische) Abhängigkeiten bestehen. Eine topologische Sortierung muss nicht eindeutig sein.

Wenn die Beziehungen vollständig sind, also für je zwei Objekte eine Abhängigkeit vorgegeben ist, so geht die topologische Sortierung in eine gewöhnliche Sortierung über.

<div class="mw-heading mw-heading2"><h2 id="Indirektes_Sortieren">Indirektes Sortieren</h2></div>

In den Fällen, bei denen das Umstellen der Daten mit hohem Aufwand verbunden ist, kann man auch indirektes Sortieren anwenden. Man benötigt dazu zusätzlichen Speicher proportional zur Anzahl der Elemente (bspw. einen <a href="Zeiger_(Informatik)" title="Zeiger (Informatik)">Zeiger</a> auf das jeweilige Element, oder dessen Indexnummer im Basis-Array). Dann wird dieses <a href="Array_(Datentyp)" title="Array (Datentyp)">Array</a> sortiert und stellt somit einen (gemäß dem Vergleichskriterium) sortierten <a href="Datenbankindex" title="Datenbankindex">Index</a> dar. Sollen die eigentlichen Daten anschließend ebenfalls in die richtige Reihenfolge gebracht werden, ist ein zusätzlicher Aufwand von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta \left(n\right)}">

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta \left(n\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e28f21ea5b5690e06e43c6cb237bd0709dd36cd3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.399ex; height:2.843ex;" alt="{\displaystyle \Theta \left(n\right)}" loading="lazy"> erforderlich.

Ist auch der (wahlfreie) Zugriff auf die Elemente „teuer“, so werden mitunter auch diejenigen Datenkomponenten in den Index übernommen, die in den Sortierschlüssel einfließen/der Sortierschlüssel sind. Dies benötigt dann weiteren zusätzlichen Speicherplatz.

<div class="mw-heading mw-heading2"><h2 id="Beweis_der_unteren_Schranke_für_vergleichsbasiertes_Sortieren">Beweis der unteren Schranke für vergleichsbasiertes Sortieren</h2></div>

Es lässt sich beweisen, dass ein vergleichsbasiertes Sortierverfahren nicht schneller als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (n\cdot \log(n))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/974c775da98bbabc8faf2699fc2574992c0cdfc7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.737ex; height:2.843ex;" alt="{\displaystyle \Omega (n\cdot \log(n))}" loading="lazy"> sein kann:

Sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> der <a href="Entscheidungsbaum" title="Entscheidungsbaum">Entscheidungsbaum</a> für die Zahlenfolge <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X=(x_{1},\ldots ,x_{n})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X=(x_{1},\ldots ,x_{n})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e4c8bfcbba2e4cc7ee6e340eb2f9022de13dcaab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.998ex; height:2.843ex;" alt="{\displaystyle X=(x_{1},\ldots ,x_{n})}" loading="lazy">. Da alle Permutationen von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> das Ergebnis des Sortieralgorithmus sein könnten, muss der Entscheidungsbaum <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> mindestens <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n!}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n!}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bae971720be3cc9b8d82f4cdac89cb89877514a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.042ex; height:2.176ex;" alt="{\displaystyle n!}" loading="lazy"> Blätter haben.

Da eine Mindestanzahl von Schritten gesucht ist, treten im Entscheidungsbaum keine unnötigen Vergleiche auf.

In einem Entscheidungsbaum mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n!}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n!}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bae971720be3cc9b8d82f4cdac89cb89877514a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.042ex; height:2.176ex;" alt="{\displaystyle n!}" loading="lazy"> Blättern beträgt die maximale und die mittlere Tiefe eines Blattes mindestens <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log(n!)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log(n!)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a0f429974f9df24d255f098a432b0c4f1cde90a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.823ex; height:2.843ex;" alt="{\displaystyle \log(n!)}" loading="lazy">.

Da eine untere Schranke gesucht ist, kann <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n!}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n!}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bae971720be3cc9b8d82f4cdac89cb89877514a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.042ex; height:2.176ex;" alt="{\displaystyle n!}" loading="lazy"> mittels <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n!\geq \left({\frac {n}{2}}\right)^{n/2}}">

<msup>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n!\geq \left({\frac {n}{2}}\right)^{n/2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c30b5a07ce899cd07f6987779b8cc26c61c16093.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:13.009ex; height:5.343ex;" alt="{\displaystyle n!\geq \left({\frac {n}{2}}\right)^{n/2}}" loading="lazy"> nach unten hin abgeschätzt werden. Damit gilt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log(n!)\geq \left({\frac {n}{2}}\right)\cdot \log \left({\frac {n}{2}}\right)=\Omega (n\cdot \log(n))}">

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log(n!)\geq \left({\frac {n}{2}}\right)\cdot \log \left({\frac {n}{2}}\right)=\Omega (n\cdot \log(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6b60ed58b9e30d39fb03da70d25e39617d9c0983.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:40.42ex; height:4.843ex;" alt="{\displaystyle \log(n!)\geq \left({\frac {n}{2}}\right)\cdot \log \left({\frac {n}{2}}\right)=\Omega (n\cdot \log(n))}" loading="lazy">.

Es bleibt noch zu zeigen, dass in einem <a href="Bin%C3%A4rbaum" title="Binärbaum">Binärbaum</a> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> Blättern die maximale und die mittlere Tiefe eines Blattes mindestens <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log(k)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log(k)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1ce0b996e36e7036153d079831aa1212eb93e67d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.992ex; height:2.843ex;" alt="{\displaystyle \log(k)}" loading="lazy"> beträgt. Angenommen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> sei ein Binärbaum, für welchen die obige Aussage nicht gilt. Seien <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2f304724948a3ef606c4a92459e22b87a954d993.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d1ba5f12fbb0ff766aec6e22148b429373608555.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}" loading="lazy"> Teilbäume eines Binärbaumes mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k>2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k>2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fa7a4bb0e17a911cb4b3f6c4e455be472a295299.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.472ex; height:2.176ex;" alt="{\displaystyle k>2}" loading="lazy"> Blättern. Für die Anzahl der Blätter <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/376315fd4983f01dada5ec2f7bebc48455b14a66.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.265ex; height:2.509ex;" alt="{\displaystyle k_{1}}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2f304724948a3ef606c4a92459e22b87a954d993.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}" loading="lazy"> bzw. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c51b4ba57ee596d8435fc4ed76703ca3a2fc444a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.265ex; height:2.509ex;" alt="{\displaystyle k_{2}}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d1ba5f12fbb0ff766aec6e22148b429373608555.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}" loading="lazy"> gilt nun offensichtlich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{1}<k}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k_{1}<k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7db8c37489308ef1157fe381e950f46dc5c140c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.575ex; height:2.509ex;" alt="{\displaystyle k_{1}<k}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{2}<k}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k_{2}<k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/97bd6fd63220520309c95ff393419682c5914419.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.575ex; height:2.509ex;" alt="{\displaystyle k_{2}<k}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{1}+k_{2}=k}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k_{1}+k_{2}=k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ab869cce3c86b255b909c4b119b2874b8e8c84a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.681ex; height:2.509ex;" alt="{\displaystyle k_{1}+k_{2}=k}" loading="lazy">.

Für die Tiefe jedes Blattes, bezogen auf die Wurzel von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy">, gilt:

<mtr>

<mtd>

<mtext>mittlere Tiefe</mtext>

</mrow>

</mtd>

<mtd>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

<msub>

<mtext>tiefe</mtext>

</mrow>

<mtext>mittlere</mtext>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

<msub>

<mtext>tiefe</mtext>

</mrow>

<mtext>mittlere</mtext>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mfrac>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{mittlere Tiefe}}(B)&={\frac {k_{1}}{k}}\cdot ({\text{tiefe}}_{\text{mittlere}}(T_{1})+1)+{\frac {k_{2}}{k}}\cdot ({\text{tiefe}}_{\text{mittlere}}(T_{2})+1)\\&\geq {\frac {k_{1}}{k}}\cdot (\log(k_{1})+1)+{\frac {k_{2}}{k}}\cdot (\log(k_{2})+1)\\&={\frac {1}{k}}\cdot (k_{1}\cdot \log(2\cdot k_{1})+k_{2}\cdot \log(2\cdot k_{2}))\end{aligned}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1edcf043a7ad0bbfeedec11975e5c83e818e12c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -7.392ex; margin-bottom: -0.279ex; width:74.045ex; height:16.509ex;" alt="{\displaystyle {\begin{aligned}{\text{mittlere Tiefe}}(B)&={\frac {k_{1}}{k}}\cdot ({\text{tiefe}}_{\text{mittlere}}(T_{1})+1)+{\frac {k_{2}}{k}}\cdot ({\text{tiefe}}_{\text{mittlere}}(T_{2})+1)\\&\geq {\frac {k_{1}}{k}}\cdot (\log(k_{1})+1)+{\frac {k_{2}}{k}}\cdot (\log(k_{2})+1)\\&={\frac {1}{k}}\cdot (k_{1}\cdot \log(2\cdot k_{1})+k_{2}\cdot \log(2\cdot k_{2}))\end{aligned}}}" loading="lazy"></dd></dl>

Das Minimum dieser Funktion liegt nun bei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{1}+k_{2}=k}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k_{1}+k_{2}=k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ab869cce3c86b255b909c4b119b2874b8e8c84a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.681ex; height:2.509ex;" alt="{\displaystyle k_{1}+k_{2}=k}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k_{1}=k_{2}={\frac {k}{2}}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k_{1}=k_{2}={\frac {k}{2}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3bebc058f3d68739e226d6ec0dbfb02d8d2c9978.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:12.775ex; height:5.343ex;" alt="{\displaystyle k_{1}=k_{2}={\frac {k}{2}}}" loading="lazy">. Eingesetzt in obige Formel ergibt das:

<mtext>mittlere Tiefe</mtext>

</mrow>

<mfrac>

</mfrac>

</mrow>

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{mittlere Tiefe}}(B)\geq {\frac {1}{k}}\cdot \left({\frac {k}{2}}\cdot \log(k)+{\frac {k}{2}}\cdot \log(k)\right)=\log(k)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5ba007b7fe3b3f96b467bcfd71974d4b0c20e605.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:58.886ex; height:6.176ex;" alt="{\displaystyle {\text{mittlere Tiefe}}(B)\geq {\frac {1}{k}}\cdot \left({\frac {k}{2}}\cdot \log(k)+{\frac {k}{2}}\cdot \log(k)\right)=\log(k)}" loading="lazy">.</dd></dl>

Dies ergibt einen Widerspruch zur Annahme, womit obige Aussage bewiesen ist.

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Donald E. Knuth: <cite style="font-style:italic">Sorting and Searching</cite>. In: <cite style="font-style:italic">The Art of Computer Programming</cite>. 2. Auflage. Band 3. Addison-Wesley, Boston 2003, ISBN 0-201-89685-0.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Sortierverfahren&rft.atitle=Sorting+and+Searching&rft.au=Donald+E.+Knuth&rft.btitle=The+Art+of+Computer+Programming&rft.date=2003&rft.edition=2.&rft.genre=book&rft.isbn=0201896850&rft.place=Boston&rft.pub=Addison-Wesley&rft.volume=3" style="display:none"> </li>

<li>Niklaus Wirth: <cite style="font-style:italic">Algorithmen und Datenstrukturen</cite>. 5. Auflage. Teubner Verlag, Stuttgart/Leipzig 1999, ISBN 3-519-22250-7.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Sortierverfahren&rft.au=Niklaus+Wirth&rft.btitle=Algorithmen+und+Datenstrukturen&rft.date=1999&rft.edition=5.&rft.genre=book&rft.isbn=3519222507&rft.place=Stuttgart%2FLeipzig&rft.pub=Teubner+Verlag" style="display:none"> </li>

<li>Robert Sedgewick: <cite style="font-style:italic">Algorithms in Java, Part 1–4</cite>. 3. Auflage. Addison-Wesley, Boston 2002, ISBN 0-201-36120-5.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Sortierverfahren&rft.au=Robert+Sedgewick&rft.btitle=Algorithms+in+Java%2C+Part+1-4&rft.date=2002&rft.edition=3.&rft.genre=book&rft.isbn=0201361205&rft.place=Boston&rft.pub=Addison-Wesley" style="display:none"> </li>

<li>Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: <cite style="font-style:italic">Algorithmen – Eine Einführung</cite>. 3. Auflage. Oldenbourg Verlag, München 2010, ISBN 978-3-486-59002-9 (amerikanisches Englisch: <cite class="lang" lang="en-US" dir="auto" style="font-style:italic">Introduction to Algorithms</cite>. Übersetzt von Paul Molitor).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Sortierverfahren&rft.au=Thomas+H.+Cormen%2C+Charles+Leiserson%2C+Ronald+L.+Rivest%2C+...&rft.btitle=Algorithmen+-+Eine+Einf%C3%BChrung&rft.date=2010&rft.edition=3.&rft.genre=book&rft.isbn=9783486590029&rft.place=M%C3%BCnchen&rft.pub=Oldenbourg+Verlag" style="display:none"> </li>

<li>Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: <cite style="font-style:italic">Introduction to Algorithms</cite>. 3. Auflage. The MIT Press, Cambridge MA / London 2009, ISBN 978-0-262-03384-8.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Sortierverfahren&rft.au=Thomas+H.+Cormen%2C+Charles+Leiserson%2C+Ronald+L.+Rivest%2C+...&rft.btitle=Introduction+to+Algorithms&rft.date=2009&rft.edition=3.&rft.genre=book&rft.isbn=9780262033848&rft.place=Cambridge+MA+%2F+London&rft.pub=The+MIT+Press" style="display:none"> </li>

<li>Thomas Ottmann, Peter Widmayer: <cite style="font-style:italic">Algorithmen und Datenstrukturen</cite>. 3. Auflage. Spektrum Verlag, Heidelberg/Berlin/Oxford 1996, ISBN 3-8274-0110-0.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Sortierverfahren&rft.au=Thomas+Ottmann%2C+Peter+Widmayer&rft.btitle=Algorithmen+und+Datenstrukturen&rft.date=1996&rft.edition=3.&rft.genre=book&rft.isbn=3827401100&rft.place=Heidelberg%2FBerlin%2FOxford&rft.pub=Spektrum+Verlag" style="display:none"> </li>

<li>Anany Levitin: <cite style="font-style:italic">Introduction to The Design and Analysis of Algorithms</cite>. 2. Auflage. Pearson Addison-Wesley, Boston 2007, ISBN 978-0-321-36413-5.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Sortierverfahren&rft.au=Anany+Levitin&rft.btitle=Introduction+to+The+Design+and+Analysis+of+Algorithms&rft.date=2007&rft.edition=2.&rft.genre=book&rft.isbn=9780321364135&rft.place=Boston&rft.pub=Pearson+Addison-Wesley" style="display:none"> </li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<div class="sisterproject" style="margin:0.1em 0 0 0;"><div class="noresize noviewer" style="display:inline-block; line-height:10px; min-width:1.6em; text-align:center;" aria-hidden="true" role="presentation"></div><a class="external text" href="https://commons.wikimedia.org/wiki/Category:Sort_algorithms?uselang=de">Commons: Sortieralgorithmen</a> – Sammlung von Bildern, Videos und Audiodateien</div>

<ul><li><a rel="nofollow" class="external text" href="https://www.bluffton.edu/homepages/facstaff/nesterd/java/SortingDemo.html">Quelltexte und Simulationen der Funktionsweise von Sortierverfahren (Bluffton University)</a></li>

<li><a rel="nofollow" class="external text" href="http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/sortcontest/sortcontest.htm">Grafischer Vergleich</a> Einige Sortieralgorithmen (Java)</li>

<li><a rel="nofollow" class="external text" href="https://www.youtube.com/watch?v=kPRA0W1kECg">Video: visuelle und auditive Darstellung diverser Sortieralgorithmen (Timo Bingmann)</a> auf <a href="YouTube" title="YouTube">YouTube</a></li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-10-22" href="https://de.wikipedia.org/wiki/?title=Sortierverfahren&oldid=260810003">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>